//请判断一个链表是否为回文链表。 
//
// 示例 1: 
//
// 输入: 1->2
//输出: false 
//
// 示例 2: 
//
// 输入: 1->2->3->2->1
//输出: true
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表 双指针 
// 👍 884 👎 0

package leetcode.editor.cn;

import com.gule.gl.leetcode.editor.cn.definition.ListNode;

import java.util.Objects;
import java.util.Stack;

//Java：回文链表
public class P234PalindromeLinkedList{
    public static void main(String[] args) {
        Solution solution = new P234PalindromeLinkedList().new Solution();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        boolean palindrome = solution.isPalindrome(node1);
        System.out.println(palindrome);
        // TO TEST

        ListNode reverse = solution.reverse(node1);
        System.out.println(reverse);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode cur = head;
        ListNode fast = head;
        Stack<ListNode> stack = new Stack();
        while (Objects.nonNull(fast) && Objects.nonNull(fast.next)){
            stack.push(cur);
            fast = fast.next.next;
            cur = cur.next;
        }
        //如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步
        if(Objects.nonNull(fast)){
            //奇数
            cur = cur.next;
        }
        while (Objects.nonNull(cur)){
            ListNode pop = stack.pop();
            if(Objects.isNull(pop) || cur.val != pop.val){
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = head;
        while (Objects.nonNull(cur)){
            //1->2->3
            //1<-2<-3
            //实际改变链表方向
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
